// sequence  queue

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 32

typedef struct
{
    int data[N];
    int front; //列队的头   数组的下标
    int rear;  //列队的尾   数组的下标
} sequeue_t;

//空队列的概念：队头等于队尾
//为了区分满队和空对，队列元素个数要比数组元素个数少一个
//满队+1 等于空队
sequeue_t *create_empty_sequeue()
{
    sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t));
    memset(q->data, 0, sizeof(q->data)); //将申请的内存清空（初始化）
    q->front = q->rear = N - 1;          //指向数组的最后一个元素
    return q;
}

int sequeue_is_empty(sequeue_t *q)
{
    return (q->front == q->rear);
}

int sequeue_is_full(sequeue_t *q)
{
    //队尾 +1 == 队头，就是满队
    //任何一个数对N求余，这个数的范围就是 0 —— N-1 ;
    return ((q->rear + 1) % N == q->front); //满队
}

int sequeue_is_size(sequeue_t *q)
{
    //队尾减去队头就是元素的个数
    if (q->rear >= q->front)
    {
        return (q->rear - q->front);
    }
    else
    {
        return (N - q->front + q->rear);
    }
}

int sequeue_enqueue(sequeue_t *q, int value)
{
    if (sequeue_is_full(q))
    {
        printf("队列已满");
        return -1;
    }
    q->rear = (q->rear + 1) % N;
    q->data[q->rear] = value; //将值写入数组
    return 0;
}

int sequeue_dequeue(sequeue_t *q, int *pvalue)
{
    if (sequeue_is_empty(q))
    {
        printf("队列已空");
        return -1;
    }
    q->front = (q->front + 1) % N;
    *pvalue = q->data[q->front];
    return 0;
}

int seqstack_push(sequeue_t *q1, sequeue_t *q2, int value) /*入栈*/
{
    sequeue_enqueue(q1, value) == 0;

    return 0;
}

int seqstack_pop(sequeue_t *q1, sequeue_t *q2, int *pvalue) /*出栈*/
{
    int value;
    // 1. q1 出队列只剩下一个元素
    while (sequeue_is_size(q1) > 1)
    {
        sequeue_dequeue(q1, &value);
        sequeue_enqueue(q2, value);
    }

    // 2. 把q1中的元素出队
    sequeue_dequeue(q1, pvalue);

    // 3. 把q2中的所有元素出队到q1
    while (sequeue_is_size(q2) > 0)
    {
        sequeue_dequeue(q2, &value);
        sequeue_enqueue(q1, value);
    }

    return 0;
}

int main(int argc, char const *argv[])
{
    sequeue_t *Q1 = create_empty_sequeue();
    sequeue_t *Q2 = create_empty_sequeue();

    printf("入队顺序为:");
    for (int i = 0; i < 32; i++)
    {
        if (seqstack_push(Q1, Q2, i + 1) == 0)
        {
            printf("%d ", i + 1);
        }
    }
    printf("\n");

    printf("出队顺序为:");
    for (int i = 0, value; i < 32; i++)
    {
        if (seqstack_pop(Q1, Q2, &value) == 0)
        {
            printf("%d ", value);
        }
    }
    printf("\n");

    return 0;
}
